A parser for linear programming problems (simplex oriented)

Theodore Keloglou

@sirodoht almost everywhere


In [1]:
import antigravity

Example

What we want our function/module to input

Example

What we want our function/module to output

Regex examples


In [3]:
import re

In [4]:
re.match('''    # e.g. +12.34 or 12.34 or +12 or 12
        [\ ]*     # any number of space characters
        [\+\ ]?   # the plus sign '+' if available, and possible space chars
        [\d]+     # *at least* one digit
        [\.]?     # a dot '.' if available
        [\d]*     # any number of digits
        ''', '+12.34x1', re.VERBOSE).group(0)


Out[4]:
'+12.34'

In [5]:
re.match('''   # e.g. -12.34 or -12
        [\ ]*     # any number of space characters
        [\-]      # a minus sign '-'
        [\d]+     # one or more digits
        [\.]?     # a dot '.' if available
        [\d]*     # any number of digits
        ''', '-12.23x2', re.VERBOSE).group(0)


Out[5]:
'-12.23'

In [16]:
re.match('''   # e.g. +12x1 or 12x2
        [\ ]*      # any number of space characters
        [\+]?      # one + if available
        [a-z]      # one letter (variable name)
        [\d]+      # at least one digits
        ''', '+x3', re.VERBOSE).group(0)


Out[16]:
'+x3'

In [17]:
re.match('''   # e.g. -12x1
        [\ ]*      # any number of space characters
        [\-]       # one minus sign
        [a-z]      # one letter(variable name)
        [\d]+      # at least one digit
        ''', '-x4', re.VERBOSE).group(0)


Out[17]:
'-x4'

In [6]:
def parse_coefficients(coefficient_list, monomial):
    """
    :rtype : None
    :param coefficient_list: List in which coefficients will be stored
    :param monomial: A string (e.g. -3x1) which will be parsed to its coefficient (e.g. -3)
    """
    import re

    # Check which pattern matches. Valid are: (s)(n)lv
    #   parenthesis indicate optional existence
    #   s is + or - (absence means +)
    #   n is a number (coefficient, absence means 1)
    #   l is a lowercase latin letter (variable letter)
    #   v is a number, probably incremental (variable number)
    if re.match('''    # e.g. +12.34 or 12.34 or +12 or 12
        [\ ]*     # any number of space characters
        [\+\ ]?   # the plus sign '+' if available, and possible space chars
        [\d]+     # *at least* one digit
        [\.]?     # a dot '.' if available
        [\d]*     # any number of digits
        ''', monomial, re.VERBOSE):
        float_cast = float(re.match('[ ]*[\+ ]?[\d]+[\.]?[\d]*', monomial).group(0))
        coefficient_list.append(float_cast)
    elif re.match('''   # e.g. -12.34 or -12
        [\ ]*     # any number of space characters
        [\-]      # a minus sign '-'
        [\d]+     # one or more digits
        [\.]?     # a dot '.' if available
        [\d]*     # any number of digits
        ''', monomial, re.VERBOSE):
        float_cast = float(re.match('[ ]*[\-][\d]+[\.]?[\d]*', monomial).group(0))
        coefficient_list.append(float_cast)
    elif re.match('''   # e.g. +12x1 or 12x2
        [\ ]*      # any number of space characters
        [\+]?      # one + if available
        [a-z]      # one letter (variable name)
        [\d]+      # at least one digits
        ''', monomial, re.VERBOSE):
        coefficient_list.append(1)
    elif re.match('''   # e.g. -12x1
        [\ ]*      # any number of space characters
        [\-]       # one minus sign
        [a-z]      # one letter(variable name)
        [\d]+      # at least one digit
        ''', monomial, re.VERBOSE):
        coefficient_list.append(-1)

In [9]:
import re

input_filename = '/home/tho/data_input_file'
output_filename = '/home/tho/data_output'

# Initialize error variable
#   If error != 0 then there was a file input problem
error = 0

try:
    infile = open(input_filename)
except FileNotFoundError:
    error = 1
    print('\nInput file error: File not found.')

lines = []
if error != 1:
    for line in infile:
        lines.append(line)

    infile.close()

for line in lines:
    print(line, end='')


min x1+x2-4x3
st x1+x2+2x3<=9
   x1-3x2-x3<=20
   -x1+x2+5x3<=4
end

In [10]:
# Check if problem is max or min
minmax_line = ''
for line in lines:
    if re.match('^[ ]*max|min', line):
        minmax_line = line

minmax = 0
objective_function = ''
if re.match('^[ ]*max', minmax_line):
    minmax = 1
    objective_function = minmax_line
    objective_function = objective_function.strip('max')
elif re.match('^[ ]*min', minmax_line):
    minmax = -1
    objective_function = minmax_line
    objective_function = objective_function.strip('min')

if minmax_line == '' and minmax == 0:
    error = 2
    print('\nInput file error: Objective function not found.')
    

# Fill c-vector with objective function coefficients
c_vector = []

regex = re.compile('^[\+\- ]?[\d]*[\.]?[\d]*[a-z][\d+]')
while regex.match(objective_function):
    monomial = regex.match(objective_function).group(0)
    parse_coefficients(c_vector, monomial)
    objective_function = objective_function.replace(monomial, '', 1)

# Fill A-matrix, b-vector and Eqin using problem constraints
a_matrix = []
b_vector = []
eqin = []

st_line = ''
st_index = 0
for index, line in enumerate(lines):
    if 'st' in line:
        st_index = index
        st_line = line

if re.match('^[ ]*st', st_line):
    st_line = st_line.replace('st', '  ', 1)

if st_line == '':
    error = 3
    print('\nInput file error: Constraints line not found. No \'st\' keyword.')

while st_index < len(lines) - 1:
    sub_a_vector = []
    a_matrix.append(sub_a_vector)
    while True:
        st_line = st_line.strip(' ')
        if re.match('^[\+\- ]?[\d]*[\.]?[\d]*[a-z][\d+]', st_line):
            monomial = re.match('^[\+\- ]?[\d]*[\.]?[\d]*[a-z][\d+]', st_line).group(0)
            parse_coefficients(sub_a_vector, monomial)
            st_line = st_line.replace(monomial, '', 1)
        elif re.match('^[<>=]+', st_line):
            monomial = re.match('^[<>=]+', st_line).group(0)
            if monomial == '<=':
                eqin.append(-1)
            elif monomial == '>=':
                eqin.append(1)
            elif monomial == '=':
                eqin.append(0)
            else:
                error = 4
                print('\nInput file error: Unexpected character; expected <=, >=, = but got', monomial)
            st_line = st_line.replace(monomial, '', 1)
        elif re.match('^[\d]+', st_line):
            monomial = re.match('^[\d]+', st_line).group(0)
            int_cast = int(re.match('^[\d]+', st_line).group(0))
            b_vector.append(int_cast)
            st_line = st_line.replace(monomial, '', 1)
        else:
            if not sub_a_vector:    # Evaluates true when the are empty lines among the constraints
                a_matrix.pop()
            break

    # Increment line number and get the next one
    st_index += 1
    st_line = lines[st_index]

    # Search for final statement and no errors
    if st_line == 'end\n' and error == 0:
        print('\nFile input successful.')
        break


File input successful.

In [11]:
# Convert constraints to dual equivalents
#  '*' means free
variable_constraints = []
if minmax == -1:
    for el in eqin:
        if el == 0:
            variable_constraints.append('*')
        elif el == 1:
            variable_constraints.append('>=0')
        elif el == -1:
            variable_constraints.append('<=0')

In [12]:
a_matrix


Out[12]:
[[1, 1, 2.0], [1, -3.0, -1], [-1, 1, 5.0]]

Matrix Transpose


In [20]:
# Transpose A-matrix
a_matrix = list(zip(a_matrix))

In [18]:
a_matrix


Out[18]:
[([1, 1, 2.0],), ([1, -3.0, -1],), ([-1, 1, 5.0],)]

In [23]:
# min(max) problem's dual is max(min)
minmax = -minmax

# Write problem to output file
outfile = open(output_filename, 'w')
outfile.write('(Objective Function) b-vector: [' + ', '.join(map(str, b_vector)) + ']\n')

outfile.write('\nA-matrix: [')
thing = ''
for index, sub_a_vector in enumerate(a_matrix):
    thing += '[ ' + ', '.join(map(str, sub_a_vector)) + ']'
    if index != (len(a_matrix) - 1):
        thing += ', '
outfile.write(thing + ']\n')

outfile.write('\n(Contraints) c-vector: [' + ', '.join(map(str, c_vector)) + ']\n')
outfile.write('\n(Variable Contraints) variable_constraints-vector: [' + ', '.join(map(str, c_vector)) + ']\n')
outfile.write('\nEqin: [' + ', '.join(map(str, eqin)) + ']\n')
outfile.write('\nMinMax: [' + str(minmax) + ']\n')
outfile.close()


print('\n===Results===')

print('c-vector:', c_vector)
print('A-matrix:', a_matrix)
print('b-vector:', b_vector)
print('Variable-contraints-vector:', variable_constraints)
print('Eqin:', eqin)
print('MinMax:', minmax)


===Results===
c-vector: [1, 1, -4.0]
A-matrix: [([1, 1, 2.0],), ([1, -3.0, -1],), ([-1, 1, 5.0],)]
b-vector: [9, 20, 4]
Variable-contraints-vector: ['<=0', '<=0', '<=0']
Eqin: [-1, -1, -1]
MinMax: 1